#include "global.h"
#include "hBitStr.h"
#include "hHuffmanDetail.h"

namespace _hHuffmanDetail
{
	std::ostream& Node::fillOs(std::ostream& os) const
	{
		return os << "[" << _freq << "]";
	}

	size_t Node::calcHeight() const
	{
		size_t leftH = 0, rightH = 0;

		if (_left)
			leftH = 1 + _left->calcHeight();

		if (_right)
			rightH = 1 + _right->calcHeight();

		return leftH > rightH ? leftH : rightH;
	}

	const Node* Node::getNodeByHeight(size_t height, size_t idx) const
	{
		if (!height)
		{
			if (idx)
				return NULL;
			else
				return this;
		}

		size_t nodeMax = (size_t)exp2(height);
		if (idx >= nodeMax)
			return NULL;

		size_t nodehalf = nodeMax / 2;
		if (idx < nodehalf)
		{
			if (_left)
				return _left->getNodeByHeight(height - 1, idx);

			return NULL;
		}

		if (!_right)
			return NULL;

		return _right->getNodeByHeight(height - 1, idx - nodehalf);
	}

	std::ostream& CharNode::fillOs(std::ostream& os) const
	{
		os << "[";
		uint16_t tmp = _key;
		for (uint8_t i = 0; i < 8; ++i)
		{
			if (_key >> (7 - i) & 1)
				os << '1';
			else
				os << '0';
		}

		return Node::fillOs(os << "]");
	}

	void StrBaseNode::fillBitStr(hBitStr& outData) const
	{
		if (_pLenKeyTab)
			outData << _pLenKeyTab[0][0];
	}

	void StrNode::fillBitStr(hBitStr& outData) const
	{
		outData << _pLenKeyTab[0][_key.size()];
		for (size_t i = _key._beg; i < _key._end; ++i)
			outData << _pCharKeyTab[0][_key._str[i]];
	}

	void StrNode::fillOsStr(std::string& outData)
	{
		_val.fillString(outData);
	}

	std::ostream& StrNode::fillOs(std::ostream& os) const
	{
		os << "[" << _freq << "]";
		if (_key.size())
			os << _key;
		else
		{
			std::string outData;
			_val.fillString(outData);
			os << outData;
		}

		return os;
	}

	void LenNode::fillBitStr(hBitStr& outData) const
	{
#if 0
		if (_len == 2 || _len > 8)
			return;

		size_t tmpLen = _len;
		if (_len > 2)
			--tmpLen;

		outData << (tmpLen | 8);
#endif // 0
		outData << (_len | 4);
	}
	
	std::ostream& LenNode::fillOs(std::ostream& os) const
	{
		return os << "[" << _freq << "]" << _len;
	}

	std::ostream& FillOsTreeCallback::operator() (std::ostream& os)
	{
		init();
		fillHeightMaxData(_pTree);
		fillAllByHeightMaxData(_pTree);
		return fillOs(os);
	}

	void FillOsTreeCallback::init()
	{
		_heightMax = _pTree->calcHeight();
		_nodeMax = (size_t)exp2(_heightMax);
	}

	void FillOsTreeCallback::fillHeightMaxData(Node* pNode)
	{
		if (!pNode)
			return;

		for (size_t i = 0; i < _nodeMax; ++i)
		{
			auto& posPair = _dataPos[_heightMax][i];
			posPair.first = _curPos;

			const _hHuffmanDetail::Node* pChildNode = pNode->getNodeByHeight(_heightMax, i);
			if (pChildNode)
			{
				posPair.second = fillTreeData(pChildNode, _dataStr[_heightMax][_curPos]);
				posPair.first = (2 * _curPos + posPair.second) / 2;
				_curPos += posPair.second + formatNum;
			}
			else
			{
				posPair.first = (2 * _curPos + _nilNum) / 2;
				_curPos += _nilNum + formatNum;
			}

			freshFormatNum();
		}
	}

	void FillOsTreeCallback::fillAllByHeightMaxData(const Node* pNode)
	{
		if (!pNode)
			return;

		while (true)
		{
			if (!_heightMax)
			{
				auto& rootPosMap = _dataPos[0];
				if (!rootPosMap.empty())
					return;

				const _hHuffmanDetail::Node* pChildNode = pNode->getNodeByHeight(0, 0);
				if (!pChildNode)
					return;

				auto& rootPosPair = rootPosMap[0];
				auto& leftPosPair = _dataPos[1][0];
				auto& rightPosPair = _dataPos[1][1];
				rootPosPair.first = (leftPosPair.first + rightPosPair.first) / 2;
				rootPosPair.second = fillTreeData(
					pChildNode,
					_dataStr[0][leftPosPair.first],
					rightPosPair.first + 1 - leftPosPair.first,
					(rightPosPair.second ? NeedBitType_Right : 0) | (leftPosPair.second ? NeedBitType_Left : 0));
				return;
			}

			auto& parentPos = _dataPos[_heightMax - 1];
			auto& parentStr = _dataStr[_heightMax - 1];
			_nodeMax /= 2;
			for (size_t i = 0; i < _nodeMax; ++i)
			{
				auto& leftPosPair = _dataPos[_heightMax][2 * i];
				auto& rightPosPair = _dataPos[_heightMax][2 * i + 1];
				parentPos[i].first = (leftPosPair.first + rightPosPair.first) / 2;
				const _hHuffmanDetail::Node* pChildNode = pNode->getNodeByHeight(_heightMax - 1, i);
				if (pChildNode)
					parentPos[i].second = fillTreeData(
						pChildNode,
						parentStr[leftPosPair.first],
						rightPosPair.first + 1 - leftPosPair.first,
						(rightPosPair.second ? NeedBitType_Right : 0) | (leftPosPair.second ? NeedBitType_Left : 0));
			}

			--_heightMax;
		}
	}

	size_t FillOsTreeCallback::fillTreeData(const Node* src, std::string& dst, size_t len, size_t needFlag)
	{
		std::ostringstream tmpDataOs;
		if (src)
			src->fillOs(tmpDataOs);
		else
			tmpDataOs << "";

		size_t dataLen = tmpDataOs.str().size();
		if (len <= 2 + dataLen)
		{
			dst = tmpDataOs.str();
			return dataLen;
		}

		size_t halfLen = (len - dataLen) / 2;
		std::ostringstream tmpOs;

		if (needFlag & NeedBitType_Left)
			tmpOs << "+" << std::string(halfLen - 1, '-');
		else
			tmpOs << std::string(halfLen, ' ');

		tmpOs << tmpDataOs.str();

		if (needFlag & NeedBitType_Right)
			tmpOs << std::string(len - dataLen - halfLen - 1, '-') << "+";
		else
			tmpOs << std::string(len - dataLen - halfLen, ' ');

		dst = tmpOs.str();
		return dst.size();
	}

	std::ostream& FillOsTreeCallback::fillOs(std::ostream& os) const
	{
		for (auto& nodeMap : _dataStr)
		{
			bool hasChild = false;
			std::ostringstream tmpOs;
			size_t pos = 0;
			for (auto& node : nodeMap.second)
			{
				os << std::string(node.first - pos, ' ');
				tmpOs << std::string(node.first - pos, ' ');
				os << node.second;
				for (auto ch : node.second)
				{
					if ('+' == ch)
					{
						tmpOs << '|';
						hasChild = true;
					}
					else
						tmpOs << ' ';
				}

				pos = node.first + node.second.size();
			}

			os << std::endl;
			if (hasChild)
				os << tmpOs.str() << std::endl;
		}

		return os;
	}

	void FillOsTreeCallback::freshFormatNum()
	{
		if (formatNum == formatNum1)
			formatNum = formatNum2;
		else
			formatNum = formatNum1;
	}
}